#ifndef cathlibcpp_queue_H
#define cathlibcpp_queue_H

// File:       queue.h
// Author:     (c) Miles Sabin, 1997
// Purpose:    approximation to ANSI C++ queue template


#ifndef included_stddef_H
#define included_stddef_H
#include <stddef.h>               // for size_t
#endif

#ifndef cathlibcpp_algorithm_H
#include "algorithm.h"            // for make_heap(), push_heap(), pop_heap()
#endif

#ifndef cathlibcpp_bool_H
#include "bool.h"
#endif

#ifndef cathlibcpp_config_H
#include "config.h"
#endif


template<class Container, class value_type>
class queue
{
  friend bool operator==(queue<Container, value_type> const& lhs, queue<Container, value_type> const& rhs);
  friend bool operator< (queue<Container, value_type> const& lhs, queue<Container, value_type> const& rhs);

  public:

#   define size_type   size_t

    // accessors
    inline bool empty() const;
    inline size_type size() const;

    inline value_type const& front() const;
    inline value_type const& back() const;

    // mutators
    inline value_type& front();
    inline value_type& back();

    inline void push(value_type const& x);
    inline void pop();

  protected:

    Container c;

#   undef size_type
};


template<class Container, class value_type>
inline bool operator==(queue<Container, value_type> const& lhs, queue<Container, value_type> const& rhs);

template<class Container, class value_type>
inline bool operator< (queue<Container, value_type> const& lhs, queue<Container, value_type> const& rhs);


template<class Container, class Compare, class value_type>
class priority_queue
{
  friend bool operator==(priority_queue<Container, Compare, value_type> const& lhs, priority_queue<Container, Compare, value_type> const& rhs);
  friend bool operator< (priority_queue<Container, Compare, value_type> const& lhs, priority_queue<Container, Compare, value_type> const& rhs);

  public:

#   define size_type   size_t

    // constructors
    inline priority_queue();
    inline priority_queue(Compare const& x);
    inline priority_queue(value_type const* first, value_type const* last, Compare const& x);

    // accessors
    inline bool empty() const;
    inline size_type size() const;

    inline value_type const& top() const;

    // mutators
    inline void push(value_type const& x);
    inline void pop();

  protected:

    Container c;
    Compare comp;

#   undef size_type
};


template<class Container, class Compare, class value_type>
inline bool operator==(priority_queue<Container, Compare, value_type> const& lhs, priority_queue<Container, Compare, value_type> const& rhs);

template<class Container, class Compare, class value_type>
inline bool operator< (priority_queue<Container, Compare, value_type> const& lhs, priority_queue<Container, Compare, value_type> const& rhs);


// Implementation of queue<Container, value_type>

#define size_type   size_t

template<class Container, class value_type>
inline bool queue<Container, value_type>::empty() const
  { return c.empty(); }

template<class Container, class value_type>
inline size_type queue<Container, value_type>::size() const
  { return c.size(); }

template<class Container, class value_type>
inline value_type const& queue<Container, value_type>::front() const
  { return c.front(); }

template<class Container, class value_type>
inline value_type const& queue<Container, value_type>::back() const
  { return c.back(); }

template<class Container, class value_type>
inline value_type& queue<Container, value_type>::front()
  { return c.front(); }

template<class Container, class value_type>
inline value_type& queue<Container, value_type>::back()
  { return c.front(); }

template<class Container, class value_type>
inline void queue<Container, value_type>::push(value_type const& x)
  { c.push_back(x); }

template<class Container, class value_type>
inline void queue<Container, value_type>::pop()
  { c.pop_front(); }

#undef size_type


// Implementation of queue<Container, value_type> free fns

template<class Container, class value_type>
inline bool operator==(queue<Container, value_type> const& lhs, queue<Container, value_type> const& rhs)
{
  return lhs.c == rhs.c;
}

template<class Container, class value_type>
inline bool operator< (queue<Container, value_type> const& lhs, queue<Container, value_type> const& rhs)
{
  return lhs.c < rhs.c;
}


// Implementation of priority_queue<Container, Compare, value_type>

#define size_type   size_t

template<class Container, class Compare, class value_type>
inline priority_queue<Container, Compare, value_type>::priority_queue()
  {}

template<class Container, class Compare, class value_type>
inline priority_queue<Container, Compare, value_type>::priority_queue(Compare const& x)
  : comp(x)
  {}

template<class Container, class Compare, class value_type>
inline priority_queue<Container, Compare, value_type>::priority_queue(value_type const* first, value_type const* last, Compare const& x)
  : c(first, last),
    comp(x)
  { make_heap(c.begin(), c.end(), comp); }

template<class Container, class Compare, class value_type>
inline bool priority_queue<Container, Compare, value_type>::empty() const
  { return c.empty(); }

template<class Container, class Compare, class value_type>
inline size_type priority_queue<Container, Compare, value_type>::size() const
  { return c.size(); }

template<class Container, class Compare, class value_type>
inline value_type const& priority_queue<Container, Compare, value_type>::top() const
  { return c.front(); }

template<class Container, class Compare, class value_type>
inline void priority_queue<Container, Compare, value_type>::push(value_type const& x)
  {
    c.push_back(x);
    push_heap(c.begin(), c.end(), comp);
  }

template<class Container, class Compare, class value_type>
inline void priority_queue<Container, Compare, value_type>::pop()
  {
    pop_heap(c.begin(), c.end(), comp);
    c.pop_back();
  }

#undef size_type


// Implementation of priority_queue<Container, Compare, value_type> free fns

template<class Container, class Compare, class value_type>
inline bool operator==(priority_queue<Container, Compare, value_type> const& lhs, priority_queue<Container, Compare, value_type> const& rhs)
{
  return lhs.c == rhs.c;
}

template<class Container, class Compare, class value_type>
inline bool operator< (priority_queue<Container, Compare, value_type> const& lhs, priority_queue<Container, Compare, value_type> const& rhs)
{
  return lhs.c < rhs.c;
}

#endif

